/*
 * @Author: szx
 * @Date: 2022-03-04 12:59:59
 * @LastEditTime: 2022-03-04 13:13:16
 * @Description:
 * @FilePath: \leetcode\1800-1899\1856\1856.js
 */
/**
 * @param {number[]} nums
 * @return {number}
 */
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSumMinProduct = function (nums) {
    const len = nums.length;

    // 前缀和
    const sum = new Array(len + 1).fill(0);
    for (let i = 1; i <= len; i++) {
        sum[i] = sum[i - 1] + nums[i - 1];
    }
    console.log(sum);
    // 使用单调栈求解出左侧第个严格小于该数的元素位置，和右侧第一个严格小于该数的元素的位置
    let stack = [];
    const right = new Array(len).fill(len);
    for (let i = 0; i < len; i++) {
        while (stack.length && nums[stack[stack.length - 1]] > nums[i]) {
            right[stack[stack.length - 1]] = i;
            stack.pop();
        }
        stack.push(i);
    }
    stack = [];
    const left = new Array(len).fill(-1);
    for (let j = len - 1; j >= 0; j--) {
        while (stack.length && nums[stack[stack.length - 1]] > nums[j]) {
            left[stack[stack.length - 1]] = j;
            stack.pop();
        }
        stack.push(j);
    }
    // 根据前缀和和left， right数组进行枚举求解
    let max = BigInt(0);
    for (let k = 0; k < len; k++) {
        const total = BigInt(sum[right[k]] - sum[left[k] + 1]) * BigInt(nums[k]);
        if (max < total) {
            max = total;
        }
    }
    return max % BigInt(1000000007);
};
console.log(maxSumMinProduct([1, 2, 3, 4]));
